\documentclass[10pt,a4paper]{article}
%\fontencoding{T1}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[francais]{babel}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{lscape}
\usepackage{float}
\author{Joris Valette, Stéphanie Viaut}
\title{Rapport de projet}

\begin{document}

\maketitle
\vspace*{1.5cm}
\begin{center}
{\huge Un compilateur d’un sous-ensemble de C}\\
\vspace{6cm}
\includegraphics[height=3cm]{LogoBx1nu.png}\\
\bigskip 
\LARGE{ Université Bordeaux I}
\end{center} 

\newpage
\newpage

\tableofcontents
\newpage 

\section{Analyse lexicale (Flex)} \label{Analyse lexicale (Flex)}
Les lexèmes sont toutes les unités lexicales que nous pouvons rencontrer dans un programme source à compiler. Dans le langage proposé les lexèmes font partie d'une de ces catégories :
\begin{itemize}
\item 
Les espaces, tabulations et retours à la ligne sont ignorés.

\item 
Le lexème est une suite de plus d'un caractère (\verb|int, static, &&, <=, if, exit, etc.|). Si c'est le cas, le token correspondant à ce lexème est envoyé à Bison pour la suite du programme.

\item 
Le lexème est un caractère de ponctuation simple (\verb|';', '[', '<', etc.|). Il est envoyé directement à Bison, où un token doit exister pour chaque caractère.

\item 
Le lexème est un identifiant (une suite commençant par une lettre, suivie d'un ensemble de lettres, de chiffres, d'underscores). Cette chaîne de caractères est alors enregistrée dans la variable de bison yylval et le token '\verb|ID|' est envoyé à Bison.

\item 
Le lexème est un nombre (suite de chiffres), il est enregistré dans yylval et le token '\verb|ENTIER|' est envoyé à Bison.

\item 
Tout autre lexème renvoie une erreur.

\end{itemize}

Le nombre de lignes et de lexèmes sont comptés lors de l'analyse lexicale. Cela permet d'obtenir la ligne et le numéro du lexème lors d'une erreur syntaxique.

Tout début de commentaire dans le programme, signalé par \verb|/*|, entraîne le passage dans l'état exclusif "commentaire". Le texte commenté est entièrement ignoré jusqu'au prochain \verb|*/|.

\section{Analyse syntaxique (Bison)}
\subsection{Retouche de la grammaire}
Nous avons commencé par analyser et schématiser la grammaire qui est fourni dans le sujet et qui sert de base. Cette grammaire n'était pas LALR(1) et nous avons donc du la modifier. 

\subsubsection{La différence entre une déclaration et une fonction}

De nombreux conflits "décalage/réduction" étaient dus à des règles effaçables, c'est-à-dire qui amenaient par dérivation à une règle vide ($\varepsilon$). Par exemple, les règles suivantes créent un conflit :
\newline

\verb|<programme>| $\rightarrow$ \verb|<liste de déclarations> <liste de fonctions>|

\verb+<liste de déclarations>+ $\rightarrow \varepsilon$ \verb+| <déclaration> ; <liste de déclarations>+
\newline

En effet, si le compilateur a pour token d'avance un INT, il ne sait pas si ce int sera un premier lexème de déclaration ou de fonction. Il doit pourtant choisir à ce moment-là le décalage ou la réduction. Une solution à ce problème a été de supprimer la règle vide et de forcer une liste de déclarations à avoir toujours au moins une déclaration. Si le fichier source ne contient pas de déclaration, le non-terminal \verb|<liste de fonctions>| est directement visité. Ce qui donne les règles suivantes :
\newline

\verb+<programme>+ $\rightarrow$ \verb+<debut>+

\verb+<debut>+ $\rightarrow$ \verb+<declaration> <debut>+

\verb+<debut>+ $\rightarrow$ \verb+<fonction> <liste de fonctions>+
\newline

Ici, la gestion des règles est plus claire pour bison. De manière abstraite, le code source est divisé en deux parties : les déclarations puis les fonctions. Ainsi, en début de programme, soit bison lit une déclaration puis récursivement revient à cette même règle (nous restons dans la première partie), soit il lit une fonction puis une liste de fonctions (passage à la deuxième partie).

NB : La règle programme n'est pas utile ici, mais pour l'action sémantique qui lui est associée (l'écriture du code dans un fichier assembleur).

\subsubsection{Autres modifications}

D'autres modifications mineures ont été apportées.

\begin{itemize}
\item 
Nous avons changé la position du point-virgule pour les instructions, car certaines instructions ont besoin d'un point-virgule, d'autres non. Le langage engendré demandait donc parfois trop de points-virgules (sur un if-else typiquement). Le point-virgule a donc été déplacé à la fin de chaque instruction qui ne boucle pas (qui n'appelle pas une autre instruction), comme :
\newline

\verb+<instruction>+ $\rightarrow$ \verb+identificateur = <expression>+
\newline



\item 
Nous avons supprimé le non-terminal \verb+<opérateur binaire>+  que nous avons intégré avec les autres \verb+<expression>+.

\end{itemize}

Notre grammaire finale ressemble à cet organigramme :

\begin{figure}[H]
\center
\includegraphics[scale=0.5]{grammairenous.png} 
\caption {Grammaire finale du projet}
\end{figure}

\subsection{Règles de priorité}
Nous avons écrit des règles de précédence et d'associativité qui permettent d'éviter les conflits entre les différents opérateurs logiques: ces règles créent des priorités qui permettent à Bison de savoir quelle réduction à la priorité, et donc quelle réduction réaliser en premier. Cette étape permet de réduire le nombre de "décalage/réduction" qui sont en nombre important à ce stade du projet.

\subsection{Correction de la grammaire} \label{Correction de la grammaire}
Pour vérifier la grammaire, nous avons utilisé des programmes C (ou des extraits de programmes) simples (en adéquation avec les restrictions du sujet) que nous avons écrits. Nous avons procédé par étapes: nous avons d'abord testé les expressions de plus bas niveau (par exemple, les terminaux de "expression") jusqu'à remonter progressivement au sommet de la "hiérarchie" de la grammaire. 

Nous avons ajouté une option nommée "debug" au makefile. Pour qu'elle soit fonctionnelle, il faut dé-commenter la deuxième ligne de la fonction main de decl.y. Cette option génère l'exécutable \textit{ilovebugs}. Il remplace l'exécutable habituel \textit{decl}. Il affiche les états de la grammaire et utilise le mode "debug" de bison. On peut ainsi constater et  analyser plus précisément les décalage/réduction, et mieux comprendre les anomalies dans la grammaire.

Cette étape du projet a été fastidieuse car les erreurs se répercutent de manière exponentielle et il faut trouver la source exacte du problème. Pour nous aider, nous avons ajouté l'option "-v" dans le makefile afin que le fichier "y.output" soit créé à la compilation.

\section{Analyse sémantique: table de symboles}
Pour implémenter la table de symboles, nous avons choisit d'utiliser la même structure qu'une pile. Dès que le programme rencontre une nouvelle variable, ou une nouvelle fonction, il "push" son ID dans la pile. Par défaut, la pile est en "mode" global. Lorsque le programme rentre dans une fonction, la pile passe en "mode" local. A la sortie de la fonction, toutes les variables locales sont effacées. De cette manière, lorsqu'une variable locale et une variable globale ont le même ID, la variable locale fait un "masque" sur la variable globale car elle est plus haute dans la pile (pour chercher un ID dans une pile, on part du sommet de la pile vers la base). Lorsque la pile est pleine, elle est agrandie. Si la pile est beaucoup plus grande que le volume de données, elle est rétrécie (seulement lors d'un "pop").

\begin{figure}[H]
\center
\includegraphics[scale=0.5]{dictionnaire.png} 
\caption {Dictionnaire en mode "local" à gauche, en mode "global" à droite } 
(Base: base du dictionnaire courant, MaxDico: taille maximal du dictionnaire, Sommet: sommet du dictionnaire courant).
\end{figure}

Le code de la table de symboles est situé dans les fichiers \textit{symtab.c} et \textit{symtab.h}.

\section{Gestion des erreurs, resynchronisation}
La gestion des erreurs lors de l'analyse lexicale est décrite dans la section \ref{Analyse lexicale (Flex)}, page \pageref{Analyse lexicale (Flex)}.

Lorsque une erreur survint pendant l'analyse syntaxique, elle est signalée, puis une resynchronisation est lancée avec yyerrok. Cette resynchronisation permet signaler plusieurs erreurs en même temps et de continuer l'analyse du programme jusqu'à sa fin, 
Des "error" sont disposés à des endroits clés dans le programme: 
\begin{itemize}
\item début
\item fonction
\item corps
\item liste d'instructions
\end{itemize}
Bison reprend l'analyse à partir de la prochaine ponctuation rencontrée ( ";" pour début, corps et liste d'instructions, "{" pour fonction).

\section{Génération de code}
\subsection{Première implémentation: l'arbre}
On produit un arbre d'expressions qui évite de faire les calculs sur la pile, et les réalise dans le registre. L'implémentation semblait efficace jusqu'au moment où nous sommes tombés sur une grosse quantité de cas particuliers. La rapport complexité/efficacité n'était alors plus rentable.

\subsection{Deuxième implémentation: la pile}
L'arbre ne poussant pas, nous avons donc décidé d'utiliser une pile, ce qui semble plus adéquat avec le fonctionnement de l'assembleur.
Cette implémentation est très similaire au fonctionnement de l'X86: les données sont stockées dans une même pile qui peut être utilisées à n'importe quel moment du programme.

\subsection{Fonctions}
Le code assembleur est généré dans les fichiers \textit{codegen.c} et \textit{codegen.h}. Les fonctions sont séparés en plusieurs catégories: 
\begin{itemize}
\item créer les structures conditionnelles (if, while...)
\item comparer des entiers et réaliser des calculs
\item exécuter "exit()", "return" ...
\end{itemize}
Nous avons défini une règle: la valeur de retour est toujours situé dans \textit{\%eax} pour les fonctions. Le résultat d'une expression est, lui, "pushé" sur la pile. 
Pour produire le code, nous utilisons une fonction \textit{"concat"} qui prend en paramètre un nombre illimité de \textit{"char *"}, et dont le dernier paramètre est toujours \textit{"NULL"}. 

Actuellement, la présence d'un prototype ou de paramètres dans une fonction provoque une erreur de segmentation. Ce problème sera réglé par la suite.

\section{Conclusion}
Notre programme effectue l'analyse lexicale, l'analyse syntaxique et la gestion des erreurs correctement. Nous avons manqué de moyens pour réaliser de manière plus approfondis des tests et pour finir la partie assembleur du projet (fonction "read\_int()").

\section*{Annexe}
\subsection*{Outils de développement}
Pour réaliser notre projet, nous avons utilisé l'éditeur Emacs.

Nous avons créer un dépôt svn pour synchroniser nos sources plus facilement.

Nous avons créé un makefile qui compile le flex, le bison et le code source c de notre programme. Une option "debug" est disponible ( voir section \ref{Correction de la grammaire}, page \pageref{Correction de la grammaire}), ainsi qu'un "make clean".

\begin{flushright}
\includegraphics[scale=3]{bison.png} 
\end{flushright}

\end{document}


